package Dinamica;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;


public class HumanGeneFunctions {
	public static String linea1;
	public static String linea2;
	public static int cont = 0;
	public static int[][] matriz = new int[1000][1000];
	
	
	
	public static int it(int i, int j){
		if(matriz[i][j]!=0) return matriz[i][j];
		if(i>linea2.length()-1){
			if(!(j>linea1.length()-1)){
				int sum = 0, k = 0;
				while(!((j+k)>linea1.length()-1)){
					sum+=calcular(linea1.charAt(j+k) , 'N');
					k++;
				}
				matriz[i][j] = sum;
				return sum;
			}
			return 0;
		}
		
		if(j>linea1.length()-1){
			if(!(i>linea2.length()-1)){
				int sum = 0, k = 0;
				while(!((i+k)>linea2.length()-1)){
					sum+=calcular(linea2.charAt(i+k) , 'N');
					k++;
				}
				matriz[i][j] = sum;
				return sum;
			}
		}
		
		int val = calcular(linea2.charAt(i), linea1.charAt(j));
		int max1 = val + it(i+1 , j+1);
		int max2 =  it(i, j+1) + calcular(linea2.charAt(i),'N');
		int max3 =  it(i+1, j) + calcular(linea1.charAt(j),'N');
		int max = Math.max(max1, Math.max(max2, max3));
		matriz[i][j] = max;
		return max;
	}
	
	
	
	
	
	public static int calcular(char a, char b){
		if(a==b) return 5;
		if(a=='A'){
			if(b=='N') return -3;
			if(b=='C') return -1;
			if(b=='G') return -2;
			if(b=='T') return -1;
		}
		if(a=='C'){
			if(b=='N') return -4;
			if(b=='A') return -1;
			if(b=='G') return -3;
			if(b=='T') return -2;
		}
		if(a=='G'){
			if(b=='N') return -2;
			if(b=='A') return -2;
			if(b=='C') return -3;
			if(b=='T') return -2;
		}
		if(a=='T'){
			if(b=='N') return -1;
			if(b=='A') return -1;
			if(b=='C') return -2;
			if(b=='G') return -2;
		}
		return Integer.MIN_VALUE;
	}
	
	
	public static void main(String[] args) throws IOException {
		
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		String linea = bf.readLine();
		while((linea = bf.readLine())!=null){
				int m=Integer.parseInt(linea);	
				linea = bf.readLine();
				while(m!=0){
					
					
					linea1 = linea.substring(2,linea.length());
					linea = bf.readLine();
					linea2 = linea.substring(2,linea.length());
					System.out.println(it(0,0));
					m--;
					if(!bf.ready()) break;
				}
				
		}

		
	}
	
	
	public static void show(){
		for(int i=0; i!=10; i++){
			for(int j=0; j!=10; j++) System.out.print(matriz[i][j]+" ");
			System.out.println("");
		}
		System.out.println("");
	}
	
}
